//
//  Solution.cpp
//  Node
//
//  Created by zhangjikuan on 2020/12/3.
//  Copyright © 2020 hsgd. All rights reserved.
//

#include "Solution.hpp"
#include <string>
using namespace std;
/*
 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

 说明：你不能倾斜容器。
 */
int Solution::maxArea(vector<int> &height) {
    int i = 0, j = (int)height.size() - 1;
    int res = 0;
    while (i < j) {
        int area = min(height[i], height[j])*(j - i);
        res = max(area, res);
        if (height[i] <= height[j]) {
            ++i;
        } else {
            --j;
        }
    }
    return res;
}

/*
 * 匹配 reg
 * 动态规划的思想
 */
bool Solution::isMatch(string s, string p) {
    int m = s.size();
    int n = p.size();
    
    auto matches = [&](int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p[j - 1] == '.') {
            return true;
        }
        return s[i - 1] == p[j - 1];
    };
    
    vector<vector<int>> f(m + 1, vector<int>(n + 1));
    f[0][0] = true;
    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == '*') {
                f[i][j] |= f[i][j - 2];
                
                if (matches(i, j - 1)) {
                    f[i][j] |= f[i - 1][j];
                }
            }
            else {
                if (matches(i, j)) {
                    f[i][j] |= f[i - 1][j - 1];
                }
            }
        }
    }
    return f[m][n];
}


int Solution::removeDuplicates(vector<int> &nums) {

    // 按照官方的思路 需要快慢指针配合
    // 慢指针i 快指针j
    // 入股i指针和j指针不相等 i++ nums[i] = nums[j]
    int i = 0; // 慢指针
    int length = (int)nums.size(); // 数组长度
    if (length == 0) { // 如果长度为空直接返回
        return 0;
    }
    for (int j = 1; j < length; j++) {
        if (nums[i] != nums[j]) {
            i++;
            nums[i] = nums[j];
        }
    }

    // 时间复杂度为 O(n)
    
    return i + 1;
    
}

int Solution::maxProfit(vector<int> &prices) {
    
    // index 表示 l
    int profit = 0;
    int buy = 0;
    int shouldBuy = 1;
    int n = (int)prices.size();
 
    int dp[n][2]; // 二维数组存储是是n天的收益
    dp[0][0] = 0; // 第一天不买 收益的为0
    dp[0][1] = -prices[0]; // 第一天买的话，现在今天的钱就是投进去 收益为付 持有 的状态
    // 买与不买的状态 根据前一天决定
    // 如果dp[2][0] = max(dp[1][0], dp[1][1] + price[2] )
    // 如果dp[2][1] = max(dp[1][1], dp[1][0] - price[2] )
    for (int i = 1; i < n; i ++) {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
    }
    // 时间复杂度是 O(N), 空间复杂度是 O(N)
    return dp[n-1][0];
    
    // 2
    // 优化去除空间保存状态的开销
    // 优化 除去不必要的内存开销 时间复杂度是O(N) 内存O(1)
    int dp0 = 0;
    int dp1 = -prices[0];
    for (int i = 1; i < n; i++) {
        dp0 = max(dp0, dp1 + prices[i]);
        dp1 = max(dp1, dp0 - prices[i]);
    }
    return dp0;
    
    // 3. 贪心算
    int ans = 0;
    for (int i = 1; i < n; ++i) {
        ans += max(0, prices[i] - prices[i - 1]);
    }
    return ans;

    
    //
    // 自己这种算法，没有算法思想来指导，根据思路判断是不是持有还是卖出
    // 根据当前和之前一天的状态的关系来进行判断
    // 实质接近算法的动态规划，不过动态规划高度抽象出来了，特征，抽象了具体的过程
    
    for (int i = 1; i < n ; i ++) {
        // 先买
        if (shouldBuy) {
            if (prices[i-1] < prices[i]) {
                buy = prices[i-1];
                shouldBuy = 0;
                if (i == n - 1) {
                    profit = profit + prices[i] - buy;
                }
            }
        } else {
            if (prices[i-1] > prices[i]) {
                // 收益
                profit = profit +  prices[i-1] - buy;
                buy = 0;
                shouldBuy = 1;
            } else {
                if (i  == n - 1) {
                    profit = profit +  prices[i] - buy;
                }
            }
        }
    }
    
    
    
    return profit;
}

int Solution::maxProfit2(vector<int> &prices) {
    int n = (int)prices.size();
    int dp[n][2];
    dp[0][0] = 0;
    dp[0][1] = -prices[0];
    
    for (int i = 1; i < n; ++i) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    return dp[n - 1][0];
    
}

void Solution::rotate(vector<int> &nums, int k) {
    int n = (int)nums.size();
    k = k % n;
    int count = 0;
    for (int start = 0; count < n; start++) {
        int current = start;
        int prev = nums[start];
        do {
            int next = (current + k) % n;
            int temp = nums[next];
            nums[next] = prev;
            prev = temp;
            current = next;
            count++;
        } while (start != current);
    }
}

int Solution::singleNumber(vector<int> &nums) {
    // 分析来看，是非空数组， 其次是基数次
    // 仔细看题后可以使用异或运算
    // 时间复杂度为线性 ，空间复杂度为O(1)
    // 注意 审题 仔细阅读
    int ret = 0;
    for (auto e: nums) ret ^= e;
//
//    for (int i = 0; i < nums.size(); i ++) {
//        ret = ret ^= nums[i];
//    }
    return ret;
}

#include <unordered_map>

vector<int> Solution::intersect(vector<int> &nums1, vector<int> &nums2) {
    
    if (nums1.size() > nums2.size()) {
        return intersect(nums2, nums1);
    }
    
    // map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），
    // 红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素
    // c++ 中 unordered_map 输入散列表 [key,value]方式来存储
    unordered_map <int, int> m;
    for (int num : nums1) {
        ++m[num];
    }
    vector<int> intersection;
    for (int num : nums2) {
        if (m.count(num)) {
            intersection.push_back(num);
            --m[num];
            if (m[num] == 0) {
                m.erase(num);
            }
        }
    }
    return intersection;
    
    if (nums1.size() > nums2.size()) {
        return intersect(nums2, nums1);
    }
    
    unordered_map<int, int> map;
    for (int num : nums1) {
        ++m[num];
    }
    
    vector<int> intersection2;
    for (int num : nums2) {
        if (m.count(num)) { // m.count(num)
            intersection2.push_back(num);
            
            --m[num];
            if (m[num] == 0) {
                m.erase(num);
            }
        }
    }
    return intersection2;
    
}

vector<int> Solution::plusOne(vector<int> &digits) {
    // 考虑几个边界问题 主要考虑 +1后是否进位， 进位，当前首位进位 需要将数值添加到第一位
    // 数组的长度限制在 0 <= digits.size() <= 100
    // 0<= digits[i] <= 9
    // 在通用的模式下
    int n = (int)digits.size();
    int carry = 0;
    int ret = 0;
    for (int i = n - 1; i >= 0; i--) {
        digits[i]++;
        digits[i] = digits[i] % 10;
        if (digits[i] != 0) {
            return digits;
        }
//        ret = (digits[i] + 1)%10;
//        carry = (digits[i] + 1)/10;
//
//        if (carry == 0) {
//            digits[i] = ret;
//            break;
//        } else {
//            digits[i] = ret;
//            if (i == 0) {
//                digits.insert(digits.begin(), 1);
//            }
//        }
        
    }
    
    // 重新生成一个数组的操作
    vector<int> res(n+1, 0);
    res[0] = 1;
    
    return res;
    
    // 直接在第一个位置插入的操作
    digits.insert(digits.begin(), 1);
  
    return digits;
}

void Solution::moveZeroes(vector<int> &nums) {
    
//    int n = (int)nums.size();
//    int j = 0;
//    for (int i = 0; i < n; i++) {
//        if (nums[i] != 0) {
//            nums[j] = nums[i];
//            j++;
//        }
//    }
//
//    for (int i = j + 1; i < n; i ++) {
//        nums[i] = 0;
//    }
    
    // 运用双指针的算法思想来解决的
    
    int n = nums.size(), left = 0, right = 0;
    while (right < n) {
        if (nums[right]) {
            swap(nums[left], nums[right]);
            left++;
        }
        right++;
    }

    
}

vector<int> Solution::twoSum(vector<int> &nums, int target) {
    
    // 下面的时间复杂度为O(n^2) 效率不高
    int n = nums.size();
    for (int i = 0; i < n; i ++) {
        int other = target - nums[i];
        for (int j = i + 1; j < n; j ++) {
            if (nums[j] == other) {
                return {i, j};
            }
        }
    }
    
    // O(n)
    unordered_map<int, int> m;
    m.count(1);

    for (int i = 0; i < n; i ++) {
        int value = nums[i];
        m[value] = i;
        
    }
    
    for (int i = 0; i < n; i ++) {
        int other = target - nums[i];
        if (m[other] && m[other] != i) {
            return {i, m[other]};
        }
    }
    
    unordered_map<int, int> hashtable;
    for (int i = 0; i < nums.size(); ++i) {
        auto it = hashtable.find(target - nums[i]);
        if (it != hashtable.end()) {
            return {it->second, i};
        }
        hashtable[nums[i]] = i;
    }
    
    
    return {};
}

bool Solution::isValidSudoku(vector<vector<char> > &board) {
    
    vector<vector<int>> row (9, vector<int>(9,0));
    vector<vector<int>> col (9, vector<int>(9,0));
    vector<vector<int>> box (9, vector<int>(9,0));
    
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            if(board[i][j] == '.'){
                continue;
            }
            int val = board[i][j] - '1';
            int box_index = (i/3) * 3 + j/3;
            if(row[i][val] == 0 && col[j][val] == 0 && box[box_index][val] == 0){
                row[i][val] = 1;
                col[j][val] = 1;
                box[box_index][val] = 1;
            }
            else{
                return false;
            }
        }
    }
    return true;
    
}



void Solution::rotate(vector<vector<int> > &matrix) {

    int n = matrix.size();
    
//    vector<vector<int>> row (n, vector<int>(n));
//    // O(N^2) 空间复杂度 O(N*N)
//    for (int i = 0; i < n; i ++) {
//        for (int j = 0; j < n; j++) {
//            row[i][j] = matrix[n-j-1][i];
//        }
//    }
    

    // 如果是
    int tmp;
    for (int i = 0; i < n; i ++) {
        tmp = matrix[i][0];
        matrix[i][0] = matrix[n - i - 1][0];
        matrix[i][n - i -1] = tmp;

    }
    
    
    
    
    int pos1=0,pos2=matrix.size()-1;
    int add,temp;
    while(pos1<pos2){
        add = 0;
        while(add < pos2-pos1){
            temp = matrix[pos2-add][pos1];
            matrix[pos2-add][pos1] = matrix[pos2][pos2-add];
            matrix[pos2][pos2-add] = matrix[pos1+add][pos2];
            matrix[pos1+add][pos2] = matrix[pos1][pos1+add];
            matrix[pos1][pos1+add] = temp;
            add++;
        }  //左上角为0块，右上角为1块，右下角为2块，左下角为3块
        pos1++;
        pos2--;
    }
    
    
    
}


void Solution::reverseString(vector<char> &s) {
    // 对于字符交换位置
    
    int n = s.size();
    char tmp;
    
    int m = n%2;
    
    m = m == 0 ? n/2 : n/2 + 1;
    
    for (int i = 0 ; i < m; i ++) {
        tmp = s[i];
        s[i] = s[n-i-1];
        s[n-i-1] = tmp;
     }
    
    /// 官方给的结果
    /// 使用双指针的思路来解题
    /// 左右指针
//    int n = s.size();
    for (int left = 0, right = n - 1; left < right; ++left, --right) {
        swap(s[left], s[right]);
    }
}

int Solution::reverse(int x) {
    
    int rev = 0;
    while (x != 0) {
        int pop = x%10;
        x = x/10;
        if (rev > INT32_MAX/10 || (rev == INT32_MAX / 10 && pop > 7)) {
            return 0;
        }
        if (rev < INT32_MIN/10 || (rev == INT32_MIN / 10 && pop < -8)) {
            return 0;
        }
        
        rev = rev*10 + pop;
    }
    
    return rev;
}

int Solution::firstUniqChar(string s) {
    
    int l = (int)s.size();
    unordered_map<char, int> m;
    for (char c : s) {
        if (m[c]) {
            m[c] ++ ;
        } else {
            m[c] = 1;
        }
    }
    
    for (int i = 0; i < l; i++) {
        if (m[s[i]] == 1) {
            return i;
        }
    }
    
    return -1;
    
}

bool Solution::isAnagram(string s, string t) {
    if (s.length() != t.length()) {
        return false;
    }
    
    
    sort(s.begin(), s.end());
    
    sort(t.begin(), t.end());
    

    return s==t;

    
    unordered_map<char, int> m;
    for (char c : s) {
        if (m[c]) {
            m[c] ++ ;
        } else {
            m[c] = 1;
        }
    }
    
    for (char c : t) {
        if (m[c] >= 0) {
            m[c]--;
        }
        
        if (m[c] < 0) {
            return false;
        }
        
    }
    
    return true;
}


bool Solution::isPalindrome(string s) {

    // 双指针的思想
    string dst;
    for (int i = 0; i< s.length(); i ++) {
        if (isalpha(s[i])) {
            dst.push_back(tolower(s[i]));
        }
    }
//    for (char c : s) {
//        // s.length
//        if (isalpha(c)) {
//            dst.push_back(tolower(c));
//        }
//    }
    
    for (long left = 0, right = dst.length() - 1; left < right; left ++, right --) {
        if (dst[left] != dst[right]) {
            return false;
        }
    }
    
    return true;
    
    int n = s.size();
    int left = 0, right = n - 1;
    while (left < right) {
        while (left < right && !isalnum(s[left])) {
            ++left;
        }
        while (left < right && !isalnum(s[right])) {
            --right;
        }
        if (left < right) {
            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }
            ++left;
            --right;
        }
    }
    return true;

}

class Automation {
    string state = "start";
    unordered_map<string, vector<string>> table = {
        {"start", {"start","signed","in_number","end"}},
        {"signed",{"end","end","in_number", "end"}},
        {"in_number",{"end","end","in_number","end"}},
        {"end", {"end", "end","end","end"}}
    };
    
    int get_col(char c) {
        if (isspace(c)) return 0;
        if (c == '+' or c == '-')return 1;
        if (isdigit(c)) return 2;
        return 3;
    }
    
public:
    int sign = 1;
    long long ans = 0;
    void get(char c) {
        state = table[state][get_col(c)];
        if (state == "in_number") {
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? min(ans, (long long)INT_MAX) : min(ans, -(long long)INT_MIN);
        } else if (state == "signed") {
            sign = c == '-' ? -1 : 1;
        }
    }
    
};
int Solution::myAtoi(string s) {
    Automation automation;
    for (char c : s) {
        automation.get(c);
    }
    
    return automation.ans * automation.sign;
    
    
    
    return 0;
}

int Solution::strStr(string haystack, string needle) {

    if (needle.length() > haystack.length() ) {
        return -1;
    }
    
    if (needle.length() == 0) {
        return 0;
        
    }
    
    // 快指针和慢指针
    int startIndex = 0;
    int haystackIndex = 0;
    
    

    // 暴力
    while (haystackIndex < haystack.length()) {
        if (haystack[haystackIndex] == needle[startIndex]) {
            startIndex ++;
            if (startIndex == needle.length()) {
                return haystackIndex - startIndex + 1;
            }
        } else {
            if (startIndex > 0) {
                haystackIndex = haystackIndex - startIndex ;
                startIndex = 0;
            }
        }
        haystackIndex ++;
    }

    for (int i = 0; i < haystack.length() - needle.length(); i ++) {
        if (haystack[i] == needle[startIndex]) {
            startIndex ++;
            if (startIndex == needle.length()) {
                return i - startIndex + 1;
            }
        } else {
            if (startIndex > 0) {
                i = i - startIndex ;
                startIndex = 0;
            }
        }
    }

    return -1;
}



/// 主要的构建next数组，next数组直接都是需要
vector<int> Solution::getNext(string needle) {
    vector<int> next(needle.length(), -1);
    int i = 0, j = -1;
    while (i < needle.length() - 1) {
        if (j == - 1 || needle[i] == needle[j]) {
            i++;
            j++;
            if(needle[i]!=needle[j]){
                next[i]=j;
            } else {
                next[i]=next[j];
            }
        } else {
            j = next[j];
        }
    }
    return next;
    
}



int Solution::strStrKMP(string haystack, string needle) {
    
    if(needle.empty())return 0;
    int i=0,m=haystack.size();//文本指针i用来指示文本串
    int j=0,n=needle.size();//模式指针j用来指示模式串
    vector<int> nextVal=getNext(needle);
    while(i<m&&j<n){
        if(j==-1||needle[j]==haystack[i])i++,j++;
        else j=nextVal[j];
    }
    return j==n?i-j:-1;
}
    
    string Solution::countAndSay(int n) {
        // 递归终止条件
        if (n == 1) {
            return "1";
        }
        // 拿到上一层的字符串
        string str = countAndSay(n - 1);
        int length = str.length();
        string res;
        // 开始指针为0
        int start = 0;
        // 注意这从起始条件要和下面长度统一
        for (int i = 1; i < length + 1; i++) {
            // 字符串最后一位直接拼接
            if (i == length) {
                res = res + to_string(i - start) + str[start];
                // 直到start位的字符串和i位的字符串不同，拼接并更新start位
            } else if (str[i] != str[start] ) {
                res = res + to_string(i - start) + str[start];
                start = i;
            }
        }
        return res;
        
        
        if (map[n].length() > 0) {
            return map[n];
        }
        string s;
        if (n==1) {
            s = "1";
            map[1] = s;
            return s;
        }
        s = countAndSay(n-1);
        string resStr;
        int count = 1;
        char tmp;
        int index = 0;
        for (char c : s) {
            if (index == 0) {
                tmp = c;
            } else {
                if (tmp == c) {
                    count ++;
                    tmp = c;
                } else {
                    resStr = resStr + to_string(count) + tmp;
                    count = 1;
                    tmp = c;
                }
                
                
            }
            
            index ++;
        }
        resStr = resStr + to_string(count) + tmp;
        map[n] = resStr;
        // 量词 数字
        // 量词怎么获取，看重复的数，可以使用二维数组表示吗
        // 假设和递归性质一样
        return resStr;
    }
    
    string Solution::longestCommonPrefix(vector<string> &strs) {
        
        
      
        
        
        
        return "";
    }




void Solution::merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
    
    if ( m < n ) {
        merge(nums2, n, nums1, m);
        return;
    }
    
    // m > n
    
    int x = 0, j = 0;
    
    for (int i = 0; i < m + n; i ++) {
        if (nums1[x] < nums2[j]) {
            // 插入到
        } else {
            
        }
            
    }
    
    
}

vector<vector<int>> Solution:: transpose(vector<vector<int>>& matrix) {
    long m = matrix.size();
    long n = matrix[0].size();
    vector<vector<int>> transposed(n, vector<int>(m));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j ++) {
            transposed[j][i] = matrix[i][j];
        }
    }
    return transposed;
}


int Solution::findRepeatNumber(vector<int> &nums) {
    long n = nums.size();
    for (int i = 0; i<n; i ++) {
        for(int j = i+1 ; j < n; j++) {
            if (nums[i] == nums[j]) {
                return nums[i];
            }
        }
    }
    return 0;
    
    // 采用Hash表结构 key Value 来进行筛选
    
}

bool Solution::findNumberIn2DArray(vector<vector<int> > &matrix, int target) {
    if (matrix.size() == 0 || matrix[0].size() == 0) {
        return false;
    }
    long rows = matrix.size();
    long columns = matrix[0].size();
    int row = 0;
    long column = columns - 1;
    while (row < rows &&  column >=0) {
        int num = matrix[row][column];
        if (num == target) {
            return true;
        } else if (num > target) {
            column--;
        } else {
            row++ ;
        }
    }
    return false;
}
/**
 
 写一个程序，输出从 1 到 n 数字的字符串表示。
 1. 如果 n 是3的倍数，输出“Fizz”；
 2. 如果 n 是5的倍数，输出“Buzz”；
 3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。
 */
//vector<string> fizzBuzz(int n) {
//    
//    //声明数组
//    vector<string> result;
//
//    for (int i = 1; i<n+1; i++) {
//        if (i%3 == 0 && i%5 != 0) {
//            result.push_back("Fizz");
//        } else if(i%3 != 0 && i%5 == 0) {
//            result.push_back("Buzz");
//        } else if (i%3 == 0 && i%5 == 0) {
//            result.push_back("FizzBuzz");
//        } else{
////            result.push_back(string(i));
//        }
//    }
//  
//}


